package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/17 - 10:27 上午
 *  希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 */

import org.junit.Test;

public class ShellSorting_05 {

    @Test
    public void test() {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSortingByMoving(array);
    }


    /**
     * 我自己写的希尔排序，移动排序
     * 使用移动法，稍微复杂，效率超高
     * 插入排序的问题：如果只分一组（单纯使用插入排序），若小的数在靠后，则需要移动有序表越长
     * 但是通过分组（希尔排序），多组同时排序，将小的数放在每一组的前面，大的数集体放在每一组的后面
     * 最后再将组合并，可以规避插入排序的问题
     *
     * @param array
     * @Version 1.0
     */
    public static void shellSorting(int[] array) {

        int insertIndex;
        int insertValue;
        int groupNum = array.length;
        int groupLength;

        while (groupNum != 1) {
            /*
             * 将数组分组
             * 步长为就是组的数量
             * 逐步缩小所分的组数
             * */
            groupNum = groupNum / 2;
            /*
             * 每组的长度=数组的长度/组的数量
             * */
            groupLength = array.length / groupNum;

            /*
             * 将每一组都进行插入排序
             * */
            for (int i = 0; i < groupNum; i++) {
                /*
                 * 遍历各组中的所有元素
                 * 有序表是分组后的本组的第一个元素
                 * 无序表的开始节点为本组的第二个元素
                 *   本组的第二个元素位置 = 本组元素的起点i  +  本次分组的步长GroupNum
                 *       本组最后一个元素对应的数组下标是i+groupNum*(groupLength-1)
                 *           可以这样写j <= i+groupNum*(groupLength-1)
                 *       本组最后一个元素的后一个元素(array[本组元素的长度])对应的数组下标是i+groupNum*groupLength
                 *           也可以j < i + groupNum * groupLength
                 * */
                for (int j = i + groupNum; j < i + groupNum * groupLength; j = j + groupNum) {
                    /*
                     * 假设有序表的最后一个元素是最大值
                     *   有序表是分组后的本组的第一个元素
                     * */
                    insertIndex = j - groupNum;
                    /*
                     * 将要插入的值先取出，在while循环中，这个值的位置会因为有序表后移一位而被覆盖
                     * */
                    insertValue = array[j];
                    /*
                     * 有序表的扩展
                     * 移动法的体现之处
                     *
                     * 核心：将取出的数(insertValue)保存，然后和有序表的元素依次比较
                     *      若取出的元素比有序表元素的值还要小，则把该有序表中的元素往后移，
                     *      有序表中最大的值（有序表中的最后一位）会覆盖从无序表中取出的元素（取出的元素就和有序表相邻，
                     *              取出的元素是无序表的第一个元素）
                     *      有序表的第二大的元素（有序表的倒数第二个）会移动到有序表第一大的元素（有序表的倒数第一个）的位置
                     *      依此类推，直到从无序表取出的元素不再大于有序表中的元素，跳出while，但不能移出有序表的第1个元素(insertIndex >= i)
                     *      有序表向后移动一位之后，无序表的第一个位置被有序表的最后一个元素覆盖
                     *      而有序表中间空出了一个位置（该位置的元素移动到了与该位置相邻的下一个位置），将从无序表中取出的元素覆盖到这里即可
                     * */
                    while (insertIndex >= i && insertValue < array[insertIndex]) {
                        array[insertIndex + groupNum] = array[insertIndex];
                        insertIndex = insertIndex - groupNum;
                    }
                    /*
                     * 因为跳出while循环的时候，会将有序表的下标移动到要插入数据的位置之前一位
                     *       所以要把有序表下标向后移一位
                     * */
                    array[insertIndex + groupNum] = insertValue;

                }
            }
//            System.out.println(Arrays.toString(array));
        }
    }


    /**
     * 希尔排序最终版
     * 移动排序
     * 没有我的速度快
     *
     * @param array
     * @Version 2.0
     */
    public static void shellSortingByMoving(int[] array) {
        int insertValue = 0;
        int insertIndex;
        int test;
        /*
         * 步进逐步减小，逐渐将原来的多组融为一组
         * 当步进gap为1时
         */
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            /*
             * 要抵达本组的最后一个元素才算 将无序表的所有元素全部插入有序表
             * 本组最后一个元素所在的数组下标 = 本组第一个元素的下标 + 本组的长度            *  步进
             * thisGroup.length          = (unordered - gap)  + (array.length / gap)*  gap
             *      unordered - gap = 0
             *      最后简化为
             * thisGroup.length = array.length
             *      我之前时这样写，也可以
             *      unordered < gap * array.length / gap
             *
             * unordered:无序表开始的下标
             * ordered:有序表的下标 = unordered - gap 初始时，有序表中只有一个元素，有序表即为本组的第一个元素
             */
            for (int unordered = gap; unordered < array.length; unordered = unordered + gap) {
                /*
                 * 将要取出的值先保存，之后会这个位置会因为有序表后移而被覆盖
                 * */
                insertValue = array[unordered];
                /*
                 * 无序表的前一个元素就是有序表的最后一个元素
                 * */
                insertIndex = unordered - gap;
                /*
                 * 核心：只要有序表中insertIndex对应下标的元素还比从无序表中取出来的元素insertValue 小
                 *      就把有序表往后移动
                 */
                while (insertIndex >= 0 && insertValue < array[insertIndex]) {


                    array[insertIndex + gap] = array[insertIndex];
                    /*
                     * 这里在跳出while循环的时候会多移动一次
                     * 所以 在 array[insertIndex+gap] = insertValue;
                     *   中要(+gap)补回来才可以
                     * */
                    insertIndex = insertIndex - gap;

                }
                /*
                 * 最后将从无序表中取出的值 写入 有序表移出来的空位
                 * */
                array[insertIndex + gap] = insertValue;
                /*
                    和我的while循环一致，只不过是另外一种写法
                    test = unordered;
                    while( test - gap >= 0 && insertValue < array[test - gap] ){
                        array[test] = array[test - gap];
                        test = test - gap;
                    }
                    array[test] = insertValue;
                */
            }
//            System.out.println(Arrays.toString(array));
        }
    }

    /**
     * 老师的希尔排序(用交换法)
     *
     * @param array
     * @version 1.0
     */
    @Deprecated
    public static void shellSortingBySwapping(int[] array) {

        int temp = 0;
        /*
         * gap:步长
         *
         * */
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            /*
             * 遍历每一组
             * 都从本组的无序表中取出元素
             * 从步长开始遍历，就相当于从无序表开始遍历
             * */
            for (int i = gap; i < array.length; i++) {
                /*
                 *   每组的第1个元素为有序表，
                 * */
                for (int j = i - gap; j >= 0; j = j - gap) {
                    /*
                     * 无序表的第一个元素 array[j+gap]
                     * */
                    if (array[j + gap] < array[j]) {
                        /*
                         * 将无序表的第一个元素往前移动，有序表依次往后移
                         * 交换的方法在这里体现
                         * 核心：慢的关键原因：有序表从后往前依次减小，
                         *       把有序表的后一个元素，即无序表的第一个元素插入有序表的时候
                         *       如果有序表中的值比取出的值更小，就把两者交换
                         *       直到取出的值不再小于有序表的插入下标对应的值，则停止交换
                         *
                         *       有点向以选择的方式从无序表中选择出要插入的元素
                         *       然后和有序表的最后一个元素（有序表中最大的值）依次比较，如果取出的值比有序表的值还要小
                         *       则用 类似冒泡的方式将取出的元素移动到 不再小于 取出值的位置
                         *
                         * 因此效率第
                         * */
                        temp = array[j + gap];
                        array[j + gap] = array[j];
                        array[j] = temp;
                    }
                }
            }
//            System.out.println(Arrays.toString(array));
        }

    }


}
